﻿// 4291. 丛林之路.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>


/*
https://www.acwing.com/problem/content/4294/

丛林中有 n
 个村庄，用前 n
 个大写字母表示。

这 n
 个村庄之间修建了若干条双向道路。

这些道路使得任意两个村庄之间都是连通的。

每条道路每个月都需要花费一定的维修费用。

现在，人们想要关掉其中一些道路，使得所有村庄之间仍然能保持两两互通的前提下，每月所需的道路维修总费用尽可能少。

例如，下面给定的两张图，左图是村庄初始的道路分布，右图是关闭一些道路，使得所有村庄之间仍然能保持两两互通且每月总维修费用最少的道路分布。

1251_1.jpg

输入格式
输入最多包含不超过 100
 组测试数据。

每组数据第一行包含整数 n
。

接下来 n−1
 行，其中第 i
 行描述初始状态下，从第 i
 个村庄（用第 i
 个大写字母表示）开始修建的所有双向道路信息。首先包含第 i
 个大写字母，表示该村庄，然后包含一个整数 k
，表示从该村庄开始修建的双向道路数量。然后描述 k
 条道路，每条道路在描述时，首先包含一个大写字母，表示道路通往的村庄，然后包含一个整数，表示道路的维修费用。

注意，每条双向道路都是从编号更靠前的村庄修建至编号更靠后的村庄，所以没有从最后一个村庄开始修建的道路。

任意两个村庄之间最多只存在一条直接道路。

当输入一行单个 0
 时，表示输入结束。

输出格式
每组数据输出一行结果，一个整数，表示所需的道路维修总费用的最小可能值。

数据范围
1<n<27
,
每条道路的维修费用取值 [1,100]
。
所有道路的数量范围 [1,75]
。
每个村庄至少和 1
 个村庄直接相连，最多和 15
 个村庄直接相连。

输入样例：
9
A 2 B 12 I 25
B 3 C 10 H 40 I 8
C 2 D 18 G 55
D 1 E 44
E 2 F 60 G 38
F 0
G 1 H 35
H 1 I 35
3
A 2 B 10 C 40
B 1 C 20
0
输出样例：
216
30
*/
int main()
{
    std::cout << "Hello World!\n";
}

 